
/** binary tree traversal methods */

package dataStructures;

public class BinaryTreeTraversal
{
   /** visit method that prints the element in the node */ 
   public static void visit(BinaryTreeNode t)
      {System.out.print(t.element + " ");}

   /** preorder traversal */
   public static void preOrder(BinaryTreeNode t)
   {
      if (t != null)
      {
         visit(t);                // visit tree root
         preOrder(t.leftChild);   // do left subtree
         preOrder(t.rightChild);  // do right subtree
      }
   }

   /** inorder traversal */
   public static void inOrder(BinaryTreeNode t)
   {
      if (t != null)
      {
         inOrder(t.leftChild);   // do left subtree
         visit(t);               // visit tree root
         inOrder(t.rightChild);  // do right subtree
      }
   }

   /** postorder traversal */
   public static void postOrder(BinaryTreeNode t)
   {
      if (t != null)
      {
         postOrder(t.leftChild);   // do left subtree
         postOrder(t.rightChild);  // do right subtree
         visit(t);                 // visit tree root
      }
   }

   /** level order traversal */
   public static void levelOrder(BinaryTreeNode t)
   {
      ArrayQueue q = new ArrayQueue();
      while (t != null) 
      {
         visit(t);  // visit t
   
         // put t's children on queue
         if (t.leftChild != null) 
            q.put(t.leftChild);
         if (t.rightChild != null)
            q.put(t.rightChild);
   
         // get next node to visit
         t = (BinaryTreeNode) q.remove();
      }
    }
   public static BinaryTreeNode BinaryTreeNodecreateTreeFromInorderAndLevelOrder(String inorder,String levelorder){
   
	   BinaryTreeNode Gnode=new BinaryTreeNode(); //this node is the top of the tree
	   Object[] inOrderArray=new Object[inorder.length()]; //this array will store the inorder string
	   ArrayQueue levelOrderQueue = new ArrayQueue(levelorder.length()); //this queue will store the level order string
	   BinaryTreeNode currentNode=null; // later i will saving root node in currentNode as currentNode will change through out the programs.
	   
	   for(int i=0;i<inOrderArray.length;i++){
		   inOrderArray[i]= inorder.substring(i,i+1);
		   levelOrderQueue.put(levelorder.substring(i, i+1)); //put levelorder in queue can use the same for loop as both strings are the same length 
	   }
	   
	   Gnode.element=levelOrderQueue.remove();// set element of root to first node in level order String;
	   int numberOfItemsInQueue=inorder.length()-1;// we minus one because we already removed one element above;
	   
	   Object elementToAdd=null;
	   
	   
	   for(int i=0;i<numberOfItemsInQueue;i++)
	   {
		   currentNode=Gnode;
		   elementToAdd=levelOrderQueue.remove();
		   int j=0;
		   
		   for (;j<inOrderArray.length;j++)
		   {
			   
			   if(inOrderArray[j ].equals(elementToAdd))
			   {
				///this is the case we would like to go left of the currentNode;
				   
				   if(currentNode.leftChild==null) 
				   {
					   currentNode.leftChild=new BinaryTreeNode(elementToAdd);
					   break;
				   }
				   else 
				   {
					   currentNode=currentNode.leftChild;
					   j=0;
					   ///if the first left node from top is not null the we have to go to the next level of the tree and we get to that node we
					  ///have to go through the in order array to see where the element lie in relation to that this node  
				   }
					   	
			  }
			   else if(inOrderArray[j].equals(currentNode.element))
			   {
				  ///this is the case we would like to go right of the currentNode;
				   
				   if(currentNode.rightChild==null)
				   {
					   currentNode.rightChild=new BinaryTreeNode(elementToAdd);
					   break;
				   }
				   else 
				   {
					currentNode=currentNode.rightChild;
					j=0;
					
					///if the first right node from top is not null the we have to go to the next level of the tree and when we get to that node we
					///have to go through the in order array to see where the element lie in relation to that this node  
					
				   }
				   
			   }
			   
		   }
		   		   
	   }
	   
	   return Gnode;
   }
   /** test program */
   public static void main(String [] args)
   {
      BinaryTreeNode y = new BinaryTreeNode(new Integer(2));
      BinaryTreeNode z = new BinaryTreeNode(new Integer(3));
      //BinaryTreeNode x = new BinaryTreeNode(new Integer(1), y, z);
      
      String inorder= "gdhbeiafjc";
      String levelorder = "abcdefghij";
      BinaryTreeNode x=BinaryTreeTraversal.BinaryTreeNodecreateTreeFromInorderAndLevelOrder(inorder, levelorder);
      
      System.out.println("The elements in preorder are");
      preOrder(x);
      System.out.println();

      System.out.println("The elements in inorder are");
      inOrder(x);
      System.out.println();

      System.out.println("The elements in postorder are");
      postOrder(x);
      System.out.println();

      System.out.println("The elements in level order are");
      levelOrder(x);
   }
}
